Odd or Even
Category:Problemas Category:Problema Do Dia Category:ACM ICPC Live Archive = Problema = Link no ACM ICPC Live Archive Link no SPOJ Brasil = Resumo = A idéia do problema Odd or Even é uma disputa de par ou ímpar entre Mary e John, onde após anotarem seus resultados (números que cada um jogou) em cartas vermelhas (para John) e azuis (para Mary) houve a mistura das cartas, de maneira que não se consiga o resultado original. Portanto o problema pede que, dado o valor das cartas de ambos, decida-se a quantidade de vitórias que Mary certamente teve (mínima possível). = Análise = Um caso de teste do problema consiste em um inteiro indicando o número de partidas e os valores de cada uma das partidas para ambos os os jogadores (Mary e John), como o exemplo: 3 1 0 4 3 1 2 Neste caso, a Mary teve os valores da segunda linha (1 0 4) e o John os valores da terceira linha (3 1 2). Uma solução direta e não eficiente consiste em fazer a combinação desses valores, checando todas as possíveis soluções em uma complexidade O(n!) . Como sabe-se que um número par consiste em P(x) = 2*x e um número ímpar consiste em I(x) = 2*x + 1 , concluí-se que: # a soma de dois números pares compõe um número par, # a soma de dois números ímpares compõe um número par e # a soma de um número par com um número ímpar compõe um número ímpar. Desta forma, acumulando-se a quantidade de números pares e ímpares de ambos Mary e John, é possível concluir qual a quantidade máximo de possíveis vitórias de John (resultados pares) e vitórias de Mary (resultados ímpares). Como o problema deseja a quantidade certa de vitórias de Mary, isto representa a quantidade mínima possível de vitórias, que se obtém pela diferença entre a quantidade de jogos jogados e a quantidade máxima de vitórias de John. Desta forma o algoritmo da solução ficaria com complexidade O(n) (para acumular as quantidades de pares e ímpares de cada um), pela seguinte fórmula: sol = n - MIN(qt\_par_{mary},\ qt\_impar_{john}) - MIN(qt\_impar_{mary},\ qt\_par_{john}) Outra maneira de enxergar a solução: Queremos associar os valores pares de Mary com os valores ímpares de John (formando assim valores ímpares), reduzindo as vitórias de Mary. Se qt_par_mary qt_impar_john, conseguiremos associar todos e Mary não ganhará nenhuma vez. Mas se forem diferentes, a diferença corresponde a uma quantidade de pares de Mary que só podem se associar a pares de John (se qt_par_mary > qt_impar_john) ou ímpares de John que só podem se associar a ímpares de Mary (se qt_par_mary < qt_impar_john). Observe: qt_par_mary qt_impar_john Mary: PPPPIIII John: IIIIPPPP Comb: IIIIIIII -> 0 Pares qt_par_mary > qt_impar_john Mary: PPPP'PP'II John: IIII'PP'PP Comb: IIII'PP'II -> 2 Pares qt_par_mary < qt_impar_john Mary: PP'II'IIII John: II'II'PPPP Comb: II'PP'IIII -> 2 Pares Logo: sol = ABS(qt\_par_{mary} - qt\_impar_{john}) = Exemplo = Entrada 3 1 0 4 3 1 2 9 0 2 2 4 2 1 2 0 4 1 2 3 4 5 0 1 2 3 0 Saída 0 3 = Solução = #include #include #define MIN(a,b) ((a) < (b) ? (a) : (b)) int main(void) { int qt_odd_mary, qt_even_mary; int qt_odd_john, qt_even_john; int n, i, v; int sol; while (1) { scanf ("%d", &n); if (!n) break; qt_odd_mary = qt_odd_john = 0; qt_even_mary = qt_even_john = 0; for (i = 0; i < n; i++) { scanf ("%d", &v); if (v % 2) qt_even_mary++; else qt_odd_mary++; } for (i = 0; i < n; i++) { scanf ("%d", &v); if (v % 2) qt_even_john++; else qt_odd_john++; } sol = n - MIN(qt_even_mary, qt_odd_john) - MIN(qt_odd_mary, qt_even_john); printf ("%d\n", sol); } return 0; }